/*
 * @lc app=leetcode.cn id=378 lang=cpp
 *
 * [378] 有序矩阵中第 K 小的元素
 */

// @lc code=start

// #include <vector>
// using namespace std;

class Solution {
   public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = matrix[0][0], right = matrix[n - 1][n - 1];

        while (left <= right) {
            int mid = (right + left) / 2;
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
                    cnt++;
                }
            }
            if (cnt < k)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return left;
    }
};
// @lc code=end
